package week02

// 210. 课程表 II
// https://leetcode-cn.com/problems/course-schedule-ii/

func findOrder(numCourses int, prerequisites [][]int) []int {
    var inDeg = make(map[int]int)   // 统计每个节点入度
    // 构建图
    var graph = make(map[int][]int)
    for _, edges := range prerequisites {
        graph[edges[1]] = append(graph[edges[1]], edges[0])
        inDeg[edges[0]]++
    }
    return bfs(graph, inDeg, numCourses)
    //var ans []int
    //var visit = make(map[int]bool)
    //for n := 0; n < numCourses; n++ {
    //    ans = dfs(graph, inDeg, n, ans, visit)
    //}
    //if len(ans) == numCourses {
    //    return ans
    //}
    //return []int{}
}

func bfs(graph map[int][]int, inDeg map[int]int, numCourses int) []int {
    var ans []int
    var queue []int
    for n := 0; n < numCourses; n++ {
        if inDeg[n] == 0 {
            queue = append(queue, n)
        }
    }
    for len(queue) > 0 {
        val := queue[0]
        queue = queue[1:]
        ans = append(ans, val)
        for _, edge := range graph[val] {
            inDeg[edge]--
            if inDeg[edge] == 0 {
                queue = append(queue, edge)
            }
        }
    }

    if len(ans) == numCourses {
        return ans
    }
    return []int{}
}

func dfs(graph map[int][]int, inDeg map[int]int, n int, ans []int, visit map[int]bool) []int {
    if visit[n] {
        return ans
    }
    if inDeg[n] != 0 {
        return ans
    }

    ans = append(ans, n)
    visit[n] = true
    for _, edge := range graph[n] {
        inDeg[edge]--
        ans = dfs(graph, inDeg, edge, ans, visit)
    }
    return ans
}